package dp.maxSubArray;
/**
 * @Date 2020/04/16
 * @author 王光浩
 * @Thinking 使用DP
 * 	  状态转移方程： f(i) = Math.max(f(i-1)+f(i),f(i)) ，这样求出以每一个元素结尾的最大子序列值后
 * @ 就可以找出最大子序列。
 * @Analysis 时间复杂度O（n），空间复杂度O（1）
 */
public class MyMethodTwo {
	public int maxSubArray(int[] nums) {
		if(nums.length == 0) return -1;
		int max = nums[0];
		for(int i=1 ; i<nums.length ; i++) {
			nums[i] = Math.max(nums[i]+nums[i-1], nums[i]);
			max = max>nums[i]? max:nums[i];
		}
		return max;
	}
}
